A computer network is a geographically distributed collection of interconnected communication links and segments for transporting data between nodes, such as computers. Many types of network segments are available, with the types ranging from local area networks (LAN) to wide area networks (WAN). For example, the LAN may typically connect personal computers and workstations over dedicated, private communications links, whereas the WAN may connect large numbers of nodes over long-distance communications links, such as common carrier telephone lines. The Internet is an example of a WAN that connects disparate networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Computer networks may be further interconnected by an intermediate network node, such as a switch or router, having a plurality of ports that may be coupled to the networks. To interconnect dispersed computer networks and/or provide Internet connectivity, many organizations rely on the infrastructure and facilities of Internet Service Providers (ISPs). ISPs typically own one or more backbone networks that are configured to provide high-speed connection to the Internet. To interconnect private networks that are geographically diverse, an organization may subscribe to one or more ISPs and couple each of its private networks to the ISP's equipment. Here, the router may be utilized to interconnect a plurality of private networks or subscribers to an IP “backbone” network. Routers typically operate at the network layer of a communications protocol stack, such as the internetwork layer of the Transmission Control Protocol/Internet Protocol (TCP/IP) communications architecture.
Simple networks may be constructed using general-purpose routers interconnected by links owned or leased by ISPs. As networks become more complex with greater numbers of elements, additional structure may be required. In a complex network, structure can be imposed on routers by assigning specific jobs to particular routers. A common approach for ISP networks is to divide assignments among access routers and backbone routers. An access router provides individual subscribers access to the network by way of large numbers of relatively low-speed ports connected to the subscribers. Backbone routers, on the other hand, provide transports to Internet backbones and are configured to provide high forwarding rates on fast interfaces. ISPs may impose further physical structure on their networks by organizing them into points of presence (POP). An ISP network usually consists of a number of POPs, each of which comprises a physical location wherein a set of access and backbone routers is located.
As Internet traffic increases, the demand for access routers to handle increased density and backbone routers to handle greater throughput becomes more important. In this context, increased density denotes a greater number of subscriber ports that can be terminated on a single router. Such requirements can be met most efficiently with platforms designed for specific applications. An example of such a specifically designed platform is an aggregation router. The aggregation router, or “aggregator”, is an access router configured to provide high quality of service (QoS) and guaranteed bandwidth for both data and voice traffic destined for the Internet. The aggregator also provides a high degree of security for such traffic. These functions are considered “high-touch” features that necessitate substantial processing of the traffic by the router.
More notably, the aggregator is configured to accommodate increased density by aggregating a large number of leased lines from ISP subscribers onto a few trunk lines coupled to an Internet backbone. Increased density has a number of advantages for an ISP, including conservation of floor space, simplified network management and improved statistical performance of the network. Real estate (i.e., floor space) in a POP is typically expensive and costs associated with floor space may be lowered by reducing the number of racks needed to terminate a large number of subscriber connections. Network management may be simplified by deploying a smaller number of larger routers. Moreover, larger numbers of interfaces on the access router improve the statistical performance of a network. Packet networks are usually designed to take advantage of statistical multiplexing, capitalizing on the fact that not all links are busy all of the time. The use of larger numbers of interfaces reduces the chances that a “fluke” burst of traffic from many sources at once will cause temporary network congestion.
Examples of intermediate network device platforms that may be used as aggregation routers include the 7200 Series and 12000 Series systems available from Cisco Systems, Inc. The Cisco 7200 system embodies a centralized processing engine architecture that utilizes a shared bus as the switching fabric for servicing a plurality of subscriber input links. The Cisco 12000 gigabit switch router (GSR) system, on the other hand, is based on a high-speed distributed routing architecture that utilizes a crossbar switch fabric as its switching core.
In addition to deployment at a POP, the aggregator may be deployed in a telephone company central office. The large numbers of subscribers connected to input interface ports of the aggregator are typically small to medium sized businesses that conduct a substantial portion of their operations “on-line”, e.g., over the Internet. Each of these subscribers may connect to the aggregator over a high reliability link connection that is typically leased from, e.g., a telephone company provider. The subscriber traffic received at the input interfaces is funneled onto at least one trunk interface. That is, the aggregator essentially functions as a large “fan-in” device wherein a plurality (e.g., thousands) of relatively low-speed subscriber input links is aggregated onto a single, high-speed output trunk to a backbone network of the Internet.
Broadly stated, each input link may comprise a T1 or T3 connection, whereas the output trunk interface connection may comprise an OC-12 connection. A T1 connection has a data rate of 1.5 megabits per seconds (Mbps) and there are preferably 28 T1s to each T3 connection; a T3 connection thus has an effective data rate of approximately 42 Mbps. On the other hand, the effective data rate of an OC-12 trunk interface connection is typically 622 Mbps. As noted, the aggregator receives a plurality of subscriber inputs (e.g., 1000 T1 lines) and may aggregate them onto a single output trunk (e.g., an OC-12 link). However, not all T1 links are constantly in use and, through the use of statistical multiplexing, the number of input subscriber lines that can be disposed over a single output trunk at one time can be determined. For example, although the effective data input rate of 1000 T1 lines is greater than 1 gigabit per second (Gbps), the subset of T1 lines that is constantly in use (e.g., approximately 400 T1 lines) may be supported over a single 622 Mbps link (OC-12).
A common requirement for the aggregator involves the delivery of predictable QoS with which different kinds of traffic can be given different delay and queuing characteristics when congestion occurs in the router. QoS mechanisms are particularly important in networks where voice or other multimedia, real time traffic is carried along with traditional “elastic” data traffic, such as file transfer or e-mail. In these networks, it is important that voice traffic be delivered with a minimum of delay by allowing these packets to “jump ahead” of data traffic when congestion occurs.
In order to ensure that queuing priorities implemented in the aggregator are useful at the interfaces of the router, the buffers or queues that hold packets after queuing decisions are rendered, but before the packets are sent, should be maintained as small as possible. The use of queues after rendering of a priority decision may cause some degree of “head of line” blocking, where lower priority packets can delay the forwarding of high priority packets; accordingly, reducing the size of such queues is significant. While total elimination of head of line blocking is difficult, the effect is minimized in the aggregator by introducing a flow control mechanism with which the output interfaces can report the status of their output queues associated with their physical ports.
A quantitative measure of the amount of head of line blocking in an output queuing system can be characterized, in the case of the router where packets are transmitted, as packet delay variation (PDV). Delay variation expresses the amount of time that can elapse between the point in time at which an ideal scheduler would send a particular packet and the time at which the packet data is actually forwarded out of the router. If there is a long queue that may or may not be full after the scheduler makes its decision, the delay variation increases. In a router having packet interfaces such as T1 or Ethernet, PDV is also increased by the variable length nature of packet data. The scheduler may decide to send a particular high priority packet at an opportune time, but if it had just started to send a large low priority packet on a slow interface in a previous arbitration cycle, the high priority packet must wait until the low priority packet has completed.
A mechanism for transferring flow control information from an interface to the router (scheduler) must work for a few fast interfaces (such as gigabit Ethernet) and for a large number of slow interfaces (channelized DS3). The flow control mechanism must also send the flow control information quickly enough to minimize PDV but at the same time, it must not overwhelm the scheduler with too many flow control status updates. These constraints require a flow control system that can be configured to send either a large number of flow control information bits spread over a long interval (for low speed channelized interfaces) or a small number of flow control information bits sent rapidly (for high speed unchannelized interfaces).
Yet, it is desirable to maintain the size of the output queues as small as possible, primarily because the amount of storage in each queue is a direct component of the latency throughout the entire router. Such latency should be kept as low as possible, particularly for those subscribers requiring high QoS. Prior attempts to maintain “shallow” queues involve either eliminating the use a queue entirely at the port of a line card (thereby causing frequent idling of the port) or providing a large queue that results in uncontrollable delay. Thus, each queue should have a shallow depth equivalent to, e.g., approximately one (1) maximum data transfer unit (MTU)+min (1 MTU, flow control bit+scheduler latency). The depth of the queue depends on the speed of the interface. For example, the data rate through a DS1 interface port is 1.54 megabits per second (Mbps) and, accordingly, the depth of the output queue should be sufficient to accommodate at least 1 msec of such data traffic or 1.54 kilobits. If an interface is faster (e.g., a DS3) then more queue space is needed for the same amount of time. Therefore to ensure “good” QoS, the depths of all buffers should be controlled (i.e., kept shallow) within the router; the present invention is directed, in part, to ensuring control over such buffers.
By keeping the capacity of each output queue to less than 1 msec of its line data rate, there should be less than 1 msec of latency throughout the output buffers. However, the use of such shallow buffers requires constant status information to the scheduler in order to avoid overflow and underflow conditions. An underflow condition arises when there are potentially packets to send but no traffic is being forwarded over the line. On the other hand, an overflow condition arises when a packet to be sent cannot be stored in the buffer and is discarded. In an aggregator having thousands of output queues, each of which must be polled by the scheduler for status pertaining to its depth, a substantial amount of “overhead” control information must be transferred between the interfaces and the scheduler of the router.
One way to transmit such information is to provide additional wires that essentially comprise a separate data path in the aggregator. However, a separate data path substantially increases the cost of the aggregator because of the addition of its constituent wires. In addition, the separate data path must operate fast and efficiently because of the substantial amount of information carried thereon. The present invention is directed to a technique for efficiently transporting such flow control information between interfaces and a scheduler of an aggregator. More specifically, the present invention is directed to a mechanism for conveying per channel flow control information to a forwarding engine of an aggregator wherein the flow control information is used to manage the depths of output queues located on line cards of the aggregator.